//大数据223 范名念 202249020109
#include <stdio.h>

void print_array(int arr[],int size){
    int i;
    for (i = 0; i < size ; i++)
        printf("%d ", arr[i]);
        printf("\n");
}

void insertion_sort(int unsorted_array[],int num_elements){
    for (int j = 1; j < num_elements; j++) {
        int key=unsorted_array[j];
        int i=j-1;
        while (i>=0 && key<unsorted_array[i]){
            unsorted_array[i+1]=unsorted_array[i];
            i--;
        }
        unsorted_array[i+1]=key;
        print_array(unsorted_array,num_elements);
    }
}

int partition(int L[],int low,int high,int total_num_elements){
    int temp = L[low];
    int pivot = L[low];
    while (low<high){
        while (low<high && L[high] >= pivot){
            --high;
        }
        L[low] = L[high];
        while (low<high && L[low] <= pivot){
            ++low;
        }
        L[high]=L[low];
    }
    L[low]=temp;
    print_array(L,total_num_elements);
    return low;
}

void QSort(int L[],int low,int high,int total_num_elements){
    if(low<high){
        int pivotpos= partition(L,low,high,total_num_elements);
        QSort(L,low,pivotpos-1,total_num_elements);
        QSort(L,pivotpos+1,high,total_num_elements);
    }
}

void quick_sort(int unsorted_array[],int num_elements){
    int low=0,high=num_elements-1;
    QSort(unsorted_array,low,high,num_elements);
}

void max_heap_down(int a[],int start,int end){
    int c=start;
    int l=2*c+1;
    int tmp=a[c];
    for (; l<=end; c=l,l=2*l+1) {
        if(l<end && a[l]<a[l+1])
            l++;
        if(tmp >= a[l])
            break;
        else{
            a[c]=a[l];
            a[l]=tmp;
        }
    }
}

void heap_sort(int unsorted_array[],int num_elements){
    int i;
    int swap;
    for (i=num_elements/2-1; i >= 0 ; i--)
        max_heap_down(unsorted_array,i,num_elements-1);
    for(i=num_elements-1;i>0;i--){
        swap= unsorted_array[i];
        unsorted_array[i]=unsorted_array[0];
        unsorted_array[0]=swap;
        print_array(unsorted_array,num_elements);
        max_heap_down(unsorted_array,0,i-1);
    }
}

int main() {
    int test[10]={4,3,2,1};
    insertion_sort(test,4);
    printf("\n");
    int test1[10]={3,1,2,5,4};
    QSort(test1,0,4,5);
    printf("\n");
    int test2[10]={10,60,12,40,30,8,70};
    heap_sort(test2,7);
}
